package arraylist;
//模拟实现ArrayList(顺序表)的功能
//不写成泛型的方式,容易出错
//只是保存String类型
public class MyArrayList {
    private String[] data = null;
    //通过这个数组,来表示顺序表中有效元素的个数
    private int size = 0;
    //表示有效元素的个数
    public MyArrayList(){
        data = new String[10];
        //默认的初识容量为10
    }

    public MyArrayList(int capacity){
        if(capacity < 10){
            capacity = 10;
        }
        data = new String[capacity];
    }

    public void resize(){
        //1.创建更长的数组,新数组的长度是原来数组的1.5倍
        String[] newData = new String[data.length + (data.length>>1)];
        //2.把原来数组的元素复制到新的数组中去
        for(int i = 0;i < size;i++){
            newData[i] = data[i];
        }
        //3.使用新数组替换老数组
        data = newData;
    }

    //elem就是element的缩写
    //实施尾插操作,把新的元素添加到顺序表的末尾
    //时间复杂度为O(1),虽然可能会引发扩容操作O(N),但是认为在使用的过程中设置良好的初识容量,来降低扩容次数
    public void add(String elem){
        if(size >= data.length){
            //扩容操作
            resize();
        }
        data[size] = elem;
        size++;
        //把elem放到data的最后一个位置上,也就是下标为size的位置
    }

    //往中间位置插入,在index元素之前插入,新元素的下标是index,其后的元素后移
    //时间复杂度O(N)
    public void insert(int index,String elem){
        //首先判定index是否合法
        if(index < 0||index > size){
            throw new IndexOutOfBoundsException("Index " + index + ",Size " + size);
        }
        if(size > data.length){
            //扩容操作
            resize();
        }

        for(int i = size - 1;i >= index;i--){
            data[i + 1] = data[i];
        }
        //把新元素放到index位置
        data[index] = elem;
        size++;
    }

    //按照下标删除某个位置的数据
    public String remove(int index)
    {
        if(index < 0||index >= size){
            throw new IndexOutOfBoundsException();
        }//这是一个双重保险(double check),因为调用者不知道实现者有没有判断,实现者也不知道调用者有没有判断
        //最合适的做法就是两个人都进行判断,才能保证不出漏洞
        String elem = data[index];
        //提前复制一份,因为后面就会将其覆盖
        //这个size - 1一定要想清楚,相当于原来的最后一个元素没有动,但是size减了1
        for(int i = index;i < size - 1;i++){
            data[i] = data[i + 1];
        }
        size--;
        return elem;
    }

    //按照元素值删除某个位置的数据
    public boolean remove(String elem){
        int removePos = 0;
        for(removePos = 0;removePos < size;removePos++){
            if(data[removePos] == elem){
                break;
            }
        }
        if(removePos == size){
            return false;
        }
        for(int i = 0;i < size - 1;i++){
            data[i] = data[i + 1];
        }
        size--;
        //推荐这里直接写remove(removePos);
        return true;

    }

    //get和set
    public String get(int index){
        if(index < 0||index >= size){
            throw new IndexOutOfBoundsException("Index: " + index + ",Size: " + size);
        }//工作中可以不写,但是面试时面试官看重的是思路,要写下来
        return data[index];
    }
    public void set(int index,String elem){
        if(index < 0||index >= size){
            throw new IndexOutOfBoundsException("Index: " + index + ",Size: " + size);
        }
        data[index] = elem;
    }

    //删除所有元素
    public void clear(){
        size = 0;
    }
    //注:这里只是把对应空间标记为无效,并不是真的删除了


    public boolean contains(String elem){
        //遍历,看elem元素是否存在,存在的话,就返回true
        for(int i = 0;i < size;i++){
            if(data[i].equals(elem))
            {
                return true;
            }
        }
        return false;
        //同样可以进行代码重用
        //if(indexOf(elem)) != -1
        //return true;
    }

    public int indexOf(String elem){
        for(int i = 0;i < size;i++){
            if(data[i].equals(elem))
            {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(String elem){
        for(int i = size - 1;i >= 0;i--){
            if(data[i].equals(elem)){
                return i;
            }
        }
        return -1;
    }

    public MyArrayList subList(int fromIndex,int toIndex){
        //创建一个新的ArrayList对象,把上述区间的元素,添加到新的对象中即可
        //fromIndex == toIndex,也是可以的,相当于得到了空的空间
        //toIndex是可以等于size的,因为右边是开区间
        if(fromIndex < 0||toIndex > size||toIndex < fromIndex){
            throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ",toIndex: " + toIndex + ",size: " + size);
        }
        MyArrayList subList = new MyArrayList(toIndex - fromIndex);
        for(int i = fromIndex;i < toIndex;i++){
            String elem = this.get(i);
            //相当于get的是list里面的i
            subList.add(elem);
        }
        return subList;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(int i = 0;i < size;i++){
            stringBuilder.append(data[i]);
            if(i < size - 1){
                //如果不是最后一个元素,就加一个逗号
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

//测试扩容,打印操作,最好把每个功能的测试单独来写,这样在测试时非常清晰,也不容易搞混
    public static void test1() {
        MyArrayList list = new MyArrayList();
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        //当顺序表中的元素个数超出10个时,就会报错,这时就需要自动扩容功能
        System.out.println(list);
    }

    //测试插入元素功能
    public static void test2()
    {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("ee");
        list.insert(3,"dd");
        System.out.println(list);
    }

    //测试根据下标删除元素功能

    public static void test3()
    {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.remove(0));
        //打印删除的元素
        System.out.println(list);
        //打印删除后的顺序表
    }

    //测试按照元素值来删除某个元素
    public static void test4(){
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.remove("aa"));
        System.out.println(list);
    }
    //测试get,set,insert函数
    public static void test5(){
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.set(0,"ff");//相当于直接替换
        System.out.println(list);
        System.out.println(list.get(0));
        list.clear();
        System.out.println(list);
    }
    public static void test6() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.contains("aa"));
        System.out.println(list.indexOf("bb"));
    }
    public static void test7() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.subList(0,10));
    }
    public static void main(String[] args) {
        test1();
//        test2();
//        test3();
//        test4();
//        test5();
//        test6();
//        test7();
    }
}
